package com.gitee.wsl.collections.queue

import kotlinx.atomicfu.atomic
import kotlinx.atomicfu.atomicArrayOfNulls

/**
 * An implementation of a CircularQueue data-structure. When the number of items
 * added exceeds the maximum capacity, items that were added first are lost.
 *
 * @param <T>
 * Type of the item's to add in this queue
 * @author [Abhishek Sanoujam](mailto:asanoujam@terracottatech.com)
 * @since 1.7
</T> */
class CircularLossyQueue<T>(val m_nMaxSize: Int) {

    private val m_aCircularArray = atomicArrayOfNulls<T>(m_nMaxSize)

    private val m_aCurrentIndex = atomic(-1)


    /**
     * Adds a new item
     *
     * @param newVal
     * value to push
     */
    fun add(newVal: T) {
        val index = (m_aCurrentIndex.incrementAndGet() % m_nMaxSize)
        m_aCircularArray[index].value = newVal
    }

    /**
     * Returns an array of the current elements in the queue. The order of
     * elements is in reverse order of the order items were added.
     *
     * @param type
     * destination
     * @return An array containing the current elements in the queue. The first
     * element of the array is the tail of the queue and the last element
     * is the head of the queue
     */
    fun toArray(type: Array<T>): Array<T> {
        require(type.size <= m_nMaxSize) { "Size of array passed in cannot be greater than $m_nMaxSize" }
        val curIndex = _getCurrentIndex()
        for (k in type.indices) {
            val index = _getIndex(curIndex - k)
            type[k] = m_aCircularArray[index].value!!
        }
        return type
    }

    private fun _getIndex(index: Int): Int {
        return if (index < 0) index + m_nMaxSize else index
    }

    /**
     * Returns value at the tail of the queue
     *
     * @return Value at the tail of the queue
     */
    fun peekOrNull(): T? {
        return if (depth() == 0) null else m_aCircularArray[_getIndex(_getCurrentIndex())].value
    }

    /**
     * Returns true if the queue is empty, otherwise false
     *
     * @return true if the queue is empty, false otherwise
     */
    val isEmtpy: Boolean
        get() = depth() == 0

    private fun _getCurrentIndex(): Int {
        return (m_aCurrentIndex.value % m_nMaxSize)
    }

    /**
     * Returns the number of items currently in the queue
     *
     * @return the number of items in the queue
     */
    fun depth(): Int {
        val currInd = m_aCurrentIndex.value + 1
        return if (currInd >= m_nMaxSize) m_nMaxSize else currInd
    }
}
